//
// (C) Copyright 2009 Irantha Suwandarathna (irantha@gmail.com)
// All rights reserved.
//

/* Copyright (c) 1995-2000, The Hypersonic SQL Group.
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the Hypersonic SQL Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * This software consists of voluntary contributions made by many individuals
 * on behalf of the Hypersonic SQL Group.
 *
 *
 * For work added by the HSQL Development Group:
 *
 * Copyright (c) 2001-2008, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


using System;
using System.Collections.Generic;
using System.Text;
using EffiProzDB.Lib;

namespace EffiProzDB
{


    // fredt@users 20020221 - patch 513005 by sqlbob@users - corrections
    // fredt@users 20020225 - patch 1.7.0 - changes to support cascading deletes
    // tony_lai@users 20020820 - patch 595052 - better error message
    // fredt@users 20021205 - patch 1.7.2 - changes to method signature
    // fredt@users - patch 1.80 - reworked the interface and comparison methods

    /**
     * Implementation of an AVL tree with parent pointers _in nodes. Subclasses
     * of Node implement the tree node objects for memory or disk storage. An
     * Index has a root Node that is linked with other nodes using Java Object
     * references or file pointers, depending on Node implementation.<p>
     * An Index object also holds information on table columns (in the form of int
     * indexes) that are covered by it.(fredt@users)
     *
     * @author Thomas Mueller (Hypersonic SQL Group)
     * @version 1.8.0
     * @since Hypersonic SQL
     */
    public class Index
    {

        // types of index
        public const int MEMORY_INDEX = 0;
        public const int DISK_INDEX = 1;
        public const int POINTER_INDEX = 2;

        //// fields
        private HsqlNameManager.HsqlName indexName;
        public bool[] colCheck;
        private int[] colIndex;
        private int[] colTypes;
        public int[] pkCols;
        public int[] pkTypes;
        private bool _isUnique;    // DDL uniqueness
        private bool useRowId;
        public bool _isConstraint;
        public bool _isForward;
        public bool _isTemp;
        private Node root;
        private int depth;
        Collation collation;
        static IndexRowIterator _emptyIterator = new IndexRowIterator(null, null, null);
        IndexRowIterator updatableIterators;
        bool onCommitPreserve;
        Table table;

        /**
         * Constructor declaration
         *
         *
         * @param name HsqlNameManager.HsqlName of the index
         * @param table table of the index
         * @param column array of column indexes
         * @param type array of column types
         * @param unique is this a unique index
         * @param constraint does this index belonging to a constraint
         * @param forward is this an auto-index for an FK that refers to a table defined after this table
         * @param visColumns count of visible columns
         */
        public Index(Database database, HsqlNameManager.HsqlName name, Table table, int[] column,
                int[] colTypes, bool isPk, bool unique, bool constraint,
                bool forward, int[] pkcols, int[] pktypes, bool temp)
        {

            this.table = table;
            this.indexName = name;
            this.colIndex = column;
            this.colTypes = colTypes;
            this.pkCols = pkcols;
            this.pkTypes = pktypes;
            _isUnique = unique;
            _isConstraint = constraint;
            _isForward = forward;
            useRowId = (!_isUnique && pkCols.Length == 0)
                       || (colIndex.Length == 0);
            colCheck = table.getNewColumnCheckList();

            ArrayUtil.intIndexesToboolArray(colIndex, colCheck);

            updatableIterators = new IndexRowIterator(null, null, null);
            updatableIterators._next = updatableIterators.last =
                updatableIterators;
            collation = database.collation;
            _isTemp = temp;
            onCommitPreserve = table.onCommitPreserve;
        }

        /**
         * Returns the HsqlNameManager.HsqlName object
         */
        public   HsqlNameManager.HsqlName getName()
        {
            return indexName;
        }

        /**
         * Changes index name. Used by 'alter index rename to'. Argument isquoted
         * is true if the name was quoted _in the DDL.
         */
        public void setName(string name, bool isquoted)
        {
            indexName.rename(name, isquoted);
        }

        /**
         * Returns the count of visible columns used
         */
        public int getVisibleColumns()
        {
            return colIndex.Length;
        }

        /**
         * Is this a UNIQUE index?
         */
        public bool isUnique()
        {
            return _isUnique;
        }

        /**
         * Does this index belong to a constraint?
         */
        public bool isConstraint()
        {
            return _isConstraint;
        }

        /**
         * Returns the array containing column indexes for index
         */
        public int[] getColumns()
        {
            return colIndex;    // todo: this gives back also primary key field(s)!
        }

        /**
         * Returns the array containing column indexes for index
         */
        public int[] getColumnTypes()
        {
            return colTypes;    // todo: this gives back also primary key field(s)!
        }

        public string getColumnNameList()
        {

            string columnNameList = "";

            for (int j = 0; j < colIndex.Length; ++j)
            {
                columnNameList +=
                    table.getColumn(colIndex[j]).columnName.statementName;

                if (j < colIndex.Length - 1)
                {
                    columnNameList += ",";
                }
            }

            return columnNameList;
        }

        /**
         * Returns the node count.
         */
        public int size(Session session)
        {

            int count = 0;
            RowIterator it = firstRow(session);

            while (it.hasNext())
            {
                it.next();

                count++;
            }

            return count;
        }

        public bool isEmpty(Session session)
        {
            return getRoot(session) == null;
        }

        public int sizeEstimate()
        {

            firstRow(null);

            return (int)(1L << depth);
        }

        public void clearAll(Session session)
        {

            setRoot(session, null);

            depth = 0;
            updatableIterators._next = updatableIterators.last =
                updatableIterators;
        }

        public void clearIterators()
        {
            updatableIterators._next = updatableIterators.last =
                updatableIterators;
        }

        public void setRoot(Session session, Node node)
        {

            if (_isTemp)
            {
                session.setIndexRoot(indexName, onCommitPreserve, node);
            }
            else
            {
                root = node;
            }
        }

        public int getRoot()
        {
            return (root == null) ? -1
                                  : root.getKey();
        }

        private Node getRoot(Session session)
        {

            if (_isTemp && session != null)
            {
                return session.getIndexRoot(indexName, onCommitPreserve);
            }
            else
            {
                return root;
            }
        }

        /**
         * Insert a node into the index
         */
        public void insert(Session session, Row row, int offset)
        {

            Node n = getRoot(session);
            Node x = n;
            bool isleft = true;
            int compare = -1;

            while (true)
            {
                if (n == null)
                {
                    if (x == null)
                    {
                        setRoot(session, row.getNode(offset));

                        return;
                    }

                    set(x, isleft, row.getNode(offset));

                    break;
                }

                compare = compareRowForInsert(session, row, n.getRow());

                if (compare == 0)
                {
                    int errorCode = Trace.VIOLATION_OF_UNIQUE_INDEX;
                    string name = indexName.statementName;

                    if (_isConstraint)
                    {
                        Constraint c =
                            table.getUniqueOrPKConstraintForIndex(this);

                        if (c != null)
                        {
                            name = c.getName().name;
                            errorCode = Trace.VIOLATION_OF_UNIQUE_CONSTRAINT;
                        }
                    }

                    throw Trace.error(errorCode, new Object[] {
                    name, getColumnNameList()
                });
                }

                isleft = compare < 0;
                x = n;
                n = child(x, isleft);
            }

            balance(session, x, isleft);
        }

        /**
         * Balances part of the tree after an alteration to the index.
         */
        private void balance(Session session, Node x,
                             bool isleft)
        {

            while (true)
            {
                int sign = isleft ? 1
                                  : -1;

                x = x.getUpdatedNode();

                switch (x.getBalance() * sign)
                {

                    case 1:
                        x.setBalance(0);

                        return;

                    case 0:
                        x.setBalance(-sign);
                        break;

                    case -1:
                        Node l = child(x, isleft);

                        if (l.getBalance() == -sign)
                        {
                            replace(session, x, l);
                            set(x, isleft, child(l, !isleft));
                            set(l, !isleft, x);

                            x = x.getUpdatedNode();

                            x.setBalance(0);

                            l = l.getUpdatedNode();

                            l.setBalance(0);
                        }
                        else
                        {
                            Node r = child(l, !isleft);

                            replace(session, x, r);
                            set(l, !isleft, child(r.getUpdatedNode(), isleft));
                            set(r, isleft, l);
                            set(x, isleft, child(r.getUpdatedNode(), !isleft));
                            set(r, !isleft, x);

                            int rb = r.getUpdatedNode().getBalance();

                            x.getUpdatedNode().setBalance((rb == -sign) ? sign
                                                                        : 0);
                            l.getUpdatedNode().setBalance((rb == sign) ? -sign
                                                                       : 0);
                            r.getUpdatedNode().setBalance(0);
                        }

                        return;
                }

                x = x.getUpdatedNode();

                if (x.isRoot())
                {
                    return;
                }

                isleft = x.isFromLeft();
                x = x.getParent();
            }
        }

        /**
         * Delete a node from the index
         */
        public void delete(Session session, Node x)
        {

            if (x == null)
            {
                return;
            }

            for (IndexRowIterator it = updatableIterators._next;
                    it != updatableIterators; it = it._next)
            {
                it.updateForDelete(x);
            }

            Node n;

            if (x.getLeft() == null)
            {
                n = x.getRight();
            }
            else if (x.getRight() == null)
            {
                n = x.getLeft();
            }
            else
            {
                Node d = x;

                x = x.getLeft();

                /*
                            // todo: this can be improved

                            while (x.getRight() != null) {
                                if (Trace.STOP) {
                                    Trace.stop();
                                }

                                x = x.getRight();
                            }
                */
                for (Node temp = x; (temp = temp.getRight()) != null; )
                {
                    x = temp;
                }

                // x will be replaced with n later
                n = x.getLeft();

                // swap d and x
                int b = x.getBalance();

                x = x.getUpdatedNode();

                x.setBalance(d.getBalance());

                d = d.getUpdatedNode();

                d.setBalance(b);

                // set x.parent
                Node xp = x.getParent();
                Node dp = d.getParent();

                x = x.getUpdatedNode();

                if (d.isRoot())
                {
                    setRoot(session, x);
                }

                x.setParent(dp);

                if (dp != null)
                {
                    dp = dp.getUpdatedNode();

                    if (dp.isRight(d))
                    {
                        dp.setRight(x);
                    }
                    else
                    {
                        dp.setLeft(x);
                    }
                }

                // relink d.parent, x.left, x.right
                d = d.getUpdatedNode();

                if (d.Equals(xp))
                {
                    d.setParent(x);

                    if (d.isLeft(x))
                    {
                        x = x.getUpdatedNode();

                        x.setLeft(d);

                        Node dr = d.getRight();

                        x = x.getUpdatedNode();

                        x.setRight(dr);
                    }
                    else
                    {
                        x.setRight(d);

                        Node dl = d.getLeft();

                        x = x.getUpdatedNode();

                        x.setLeft(dl);
                    }
                }
                else
                {
                    d.setParent(xp);

                    xp = xp.getUpdatedNode();

                    xp.setRight(d);

                    Node dl = d.getLeft();
                    Node dr = d.getRight();

                    x = x.getUpdatedNode();

                    x.setLeft(dl);
                    x.setRight(dr);
                }

                x.getRight().setParent(x);
                x.getLeft().setParent(x);

                // set d.left, d.right
                d = d.getUpdatedNode();

                d.setLeft(n);

                if (n != null)
                {
                    n = n.getUpdatedNode();

                    n.setParent(d);
                }

                d = d.getUpdatedNode();

                d.setRight(null);

                x = d;
            }

            bool isleft = x.isFromLeft();

            replace(session, x, n);

            n = x.getParent();
            x = x.getUpdatedNode();

            x.delete();

            while (n != null)
            {
                x = n;

                int sign = isleft ? 1
                                  : -1;

                x = x.getUpdatedNode();

                switch (x.getBalance() * sign)
                {

                    case -1:
                        x.setBalance(0);
                        break;

                    case 0:
                        x.setBalance(sign);

                        return;

                    case 1:
                        Node r = child(x, !isleft);
                        int b = r.getBalance();

                        if (b * sign >= 0)
                        {
                            replace(session, x, r);
                            set(x, !isleft, child(r, isleft));
                            set(r, isleft, x);

                            if (b == 0)
                            {
                                x = x.getUpdatedNode();

                                x.setBalance(sign);

                                r = r.getUpdatedNode();

                                r.setBalance(-sign);

                                return;
                            }

                            x = x.getUpdatedNode();

                            x.setBalance(0);

                            r = r.getUpdatedNode();

                            r.setBalance(0);

                            x = r;
                        }
                        else
                        {
                            Node l = child(r, isleft);

                            replace(session, x, l);

                            l = l.getUpdatedNode();
                            b = l.getBalance();

                            set(r, isleft, child(l, !isleft));
                            set(l, !isleft, r);
                            set(x, !isleft, child(l, isleft));
                            set(l, isleft, x);

                            x = x.getUpdatedNode();

                            x.setBalance((b == sign) ? -sign
                                                     : 0);

                            r = r.getUpdatedNode();

                            r.setBalance((b == -sign) ? sign
                                                      : 0);

                            l = l.getUpdatedNode();

                            l.setBalance(0);

                            x = l;
                        }
                        break;
                }

                isleft = x.isFromLeft();
                n = x.getParent();
            }
        }

        public RowIterator findFirstRow(Session session, Object[] rowdata,
                                 int[] rowColMap)
        {

            Node node = findNotNull(session, rowdata, rowColMap, true);

            return getIterator(session, node); 
       
        }

        public RowIterator findFirstRowForDelete(Session session, Object[] rowdata,
                                           int[] rowColMap)
        {

            Node node = findNotNull(session, rowdata, rowColMap, true);
            IndexRowIterator it = getIterator(session, node);

            if (node != null)
            {
                updatableIterators.link(it);
            }

            return it; 

        }

        /**
         * Finds an existing row
         */
        public Row findRow(Session session, Row row)
        {

            Node node = search(session, row);

            return node == null ? null
                                : node.getRow();
        }

        public bool exists(Session session, Object[] rowdata,
                       int[] rowColMap)
        {
            return findNotNull(session, rowdata, rowColMap, true) != null;
     
        }

        public RowIterator emptyIterator()
        {
            return _emptyIterator;
      
        }

        /**
         * Finds a foreign key referencing rows (in child table)
         *
         * @param rowdata array containing data for the index columns
         * @param rowColMap map of the data to columns
         * @param first true if the first matching node is required, false if any node
         * @return matching node or null
         * @ 
         */
        private Node findNotNull(Session session, Object[] rowdata,
                                 int[] rowColMap,
                                 bool first)
        {

            Node x = getRoot(session);
            Node n;
            Node result = null;

            if (isNull(rowdata, rowColMap))
            {
                return null;
            }

            while (x != null)
            {
                int i = this.compareRowNonUnique(session, rowdata, rowColMap,
                                                 x.getData());

                if (i == 0)
                {
                    if (first == false)
                    {
                        result = x;

                        break;
                    }
                    else if (result == x)
                    {
                        break;
                    }

                    result = x;
                    n = x.getLeft();
                }
                else if (i > 0)
                {
                    n = x.getRight();
                }
                else
                {
                    n = x.getLeft();
                }

                if (n == null)
                {
                    break;
                }

                x = n;
            }

            return result;
        }

        /**
         * Finds any row that matches the rowdata. Use rowColMap to map index
         * columns to rowdata. Limit to visible columns of data.
         *
         * @param rowdata array containing data for the index columns
         * @param rowColMap map of the data to columns
         * @return node matching node
         * @ 
         */
        /*
            Node find(Object[] rowdata, int[] rowColMap)   {

                Node x = root;

                while (x != null) {
                    int c = compareRowNonUnique(rowdata, rowColMap, x.getData());

                    if (c == 0) {
                        return x;
                    } else if (c < 0) {
                        x = x.getLeft();
                    } else {
                        x = x.getRight();
                    }
                }

                return null;
            }
        */

        /**
         * Determines if a table row has a null column for any of the columns given
         * _in the rowColMap array.
         */
        public static bool isNull(Object[] row, int[] rowColMap)
        {

            int count = rowColMap.Length;

            for (int i = 0; i < count; i++)
            {
                if (row[rowColMap[i]] == null)
                {
                    return true;
                }
            }

            return false;
        }

        /**
         * Determines if a table row has a null column for any of the indexed
         * columns.
         */
        public bool isNull(Object[] row)
        {

            int count = colIndex.Length;

            for (int i = 0; i < count; i++)
            {
                int j = colIndex[i];

                if (row[j] == null)
                {
                    return true;
                }
            }

            return false;
        }

        /**
         * Return the first node equal to the rowdata object. Use visible columns
         * only. The rowdata has the same column mapping as this table.
         *
         * @param rowdata array containing table row data
         * @return iterator
         * @ 
         */
        public RowIterator findFirstRow(Session session,
                                  Object[] rowdata)
        {

            Node x = getRoot(session);
            Node found = null;
            bool unique = _isUnique && !isNull(rowdata);

            while (x != null)
            {
                int c = compareRowNonUnique(session, rowdata, colIndex,
                                            x.getData());

                if (c == 0)
                {
                    found = x;

                    if (unique)
                    {
                        break;
                    }

                    x = x.getLeft();
                }
                else if (c < 0)
                {
                    x = x.getLeft();
                }
                else
                {
                    x = x.getRight();
                }
            }

            return getIterator(session, found);

        }

        /**
         * Finds the first node that is larger or equal to the given one based
         * on the first column of the index only.
         *
         * @param value value to match
         * @param compare comparison Expression type
         *
         * @return iterator
         *
         * @ 
         */
        public RowIterator findFirstRow(Session session, Object value,
                                 int compare)
        {

            bool isEqual = compare == Expression.EQUAL
                              || compare == Expression.IS_NULL;
            Node x = getRoot(session);
            int iTest = 1;

            if (compare == Expression.BIGGER)
            {
                iTest = 0;
            }

            if (value == null && !isEqual)
            {
                return _emptyIterator;
            }

            /*
                    // this method returns the correct node only with the following conditions
                    bool check = compare == Expression.BIGGER
                                    || compare == Expression.EQUAL
                                    || compare == Expression.BIGGER_EQUAL;

                    if (!check) {
                        Trace.doAssert(false, "Index.findFirst");
                    }
            */
            while (x != null)
            {
                bool t =
                    Column.compare(
                        collation, value, x.getData()[colIndex[0]],
                        colTypes[0]) >= iTest;

                if (t)
                {
                    Node r = x.getRight();

                    if (r == null)
                    {
                        break;
                    }

                    x = r;
                }
                else
                {
                    Node l = x.getLeft();

                    if (l == null)
                    {
                        break;
                    }

                    x = l;
                }
            }

            /*
                    while (x != null
                            && Column.compare(value, x.getData()[colIndex_0], colType_0)
                               >= iTest) {
                        x = next(x);
                    }
            */
            while (x != null)
            {
                Object colvalue = x.getData()[colIndex[0]];
                int result = Column.compare(collation, value, colvalue,
                                            colTypes[0]);

                if (result >= iTest)
                {
                    x = next(x);
                }
                else
                {
                    if (isEqual)
                    {
                        if (result != 0)
                        {
                            x = null;
                        }
                    }
                    else if (colvalue == null)
                    {
                        x = next(x);

                        continue;
                    }

                    break;
                }
            }

            return getIterator(session, x);

        }

        /**
         * Finds the first node where the data is not null.
         *
         * @return iterator
         *
         * @ 
         */
        public RowIterator findFirstRowNotNull(Session session)
        {

            Node x = getRoot(session);

            while (x != null)
            {
                bool t = Column.compare(
                    collation, null, x.getData()[colIndex[0]], colTypes[0]) >= 0;

                if (t)
                {
                    Node r = x.getRight();

                    if (r == null)
                    {
                        break;
                    }

                    x = r;
                }
                else
                {
                    Node l = x.getLeft();

                    if (l == null)
                    {
                        break;
                    }

                    x = l;
                }
            }

            while (x != null)
            {
                Object colvalue = x.getData()[colIndex[0]];

                if (colvalue == null)
                {
                    x = next(x);
                }
                else
                {
                    break;
                }
            }

            return getIterator(session, x);
        }

        /**
         * Returns the row for the first node of the index
         *
         * @return Iterator for first row
         *
         * @ 
         */
        public RowIterator firstRow(Session session)
        {

            depth = 0;

            Node x = getRoot(session);
            Node l = x;

            while (l != null)
            {
                x = l;
                l = x.getLeft();

                depth++;
            }

            return getIterator(session, x); 
   
        }

        /**
         * Returns the row for the last node of the index
         *
         * @return last row
         *
         * @ 
         */
        public Row lastRow(Session session)
        {

            Node x = getRoot(session);
            Node l = x;

            while (l != null)
            {
                x = l;
                l = x.getRight();
            }

            return x == null ? null
                             : x.getRow();
        }

        /**
         * Returns the node after the given one
         *
         * @param x node
         *
         * @return next node
         *
         * @ 
         */
        public Node next(Node x)
        {

            if (x == null)
            {
                return null;
            }

            Node r = x.getRight();

            if (r != null)
            {
                x = r;

                Node l = x.getLeft();

                while (l != null)
                {
                    x = l;
                    l = x.getLeft();
                }

                return x;
            }

            Node ch = x;

            x = x.getParent();

            while (x != null && ch.Equals(x.getRight()))
            {
                ch = x;
                x = x.getParent();
            }

            return x;
        }

        /**
         * Returns either child node
         *
         * @param x node
         * @param isleft bool
         *
         * @return child node
         *
         * @ 
         */
        private Node child(Node x, bool isleft)
        {
            return isleft ? x.getLeft()
                          : x.getRight();
        }

        /**
         * Replace two nodes
         *
         * @param x node
         * @param n node
         *
         * @ 
         */
        private void replace(Session session, Node x,
                             Node n)
        {

            if (x.isRoot())
            {
                if (n != null)
                {
                    n = n.getUpdatedNode();

                    n.setParent(null);
                }

                setRoot(session, n);
            }
            else
            {
                set(x.getParent(), x.isFromLeft(), n);
            }
        }

        /**
         * Set a node as child of another
         *
         * @param x parent node
         * @param isleft bool
         * @param n child node
         *
         * @ 
         */
        private void set(Node x, bool isleft, Node n)
        {

            x = x.getUpdatedNode();

            if (isleft)
            {
                x.setLeft(n);
            }
            else
            {
                x.setRight(n);
            }

            if (n != null)
            {
                n = n.getUpdatedNode();

                n.setParent(x);
            }
        }

        /**
         * Find a node with matching data
         *
         * @param row row data
         *
         * @return matching node
         *
         * @ 
         */
        private Node search(Session session, Row row)
        {

        //   Object[] d = row.getData();
            Node x = getRoot(session);

            while (x != null)
            {
                int c = compareRowForInsert(session, row, x.getRow());

                if (c == 0)
                {
                    return x;
                }
                else if (c < 0)
                {
                    x = x.getLeft();
                }
                else
                {
                    x = x.getRight();
                }
            }

            return null;
        }

        /**
         * Compares two table rows based on the columns of this index. The rowColMap
         * parameter specifies which columns of the other table are to be compared
         * with the colIndex columns of this index. The rowColMap can cover all
         * or only some columns of this index.
         *
         * @param a row from another table
         * @param rowColMap column indexes _in the other table
         * @param b a full row _in this table
         *
         * @return comparison result, -1,0,+1
         * @ 
         */
        public int compareRowNonUnique(Session session, Object[] a, int[] rowColMap,
                                Object[] b)
        {

            int i = Column.compare(collation, a[rowColMap[0]], b[colIndex[0]],
                                   colTypes[0]);

            if (i != 0)
            {
                return i;
            }

            int fieldcount = rowColMap.Length;

            for (int j = 1; j < fieldcount; j++)
            {
                i = Column.compare(collation, a[rowColMap[j]], b[colIndex[j]],
                                   colTypes[j]);

                if (i != 0)
                {
                    return i;
                }
            }

            return 0;
        }

        /**
         * compares two full table rows based on a set of columns
         *
         * @param a a full row
         * @param b a full row
         * @param cols array of column indexes to compare
         *
         * @return comparison result, -1,0,+1
         * @ 
         */
        public static int compareRows(Session session, Object[] a, Object[] b,
                               int[] cols, int[] coltypes)
        {

            int fieldcount = cols.Length;

            for (int j = 0; j < fieldcount; j++)
            {
                int i = Column.compare(session.database.collation, a[cols[j]],
                                       b[cols[j]], coltypes[cols[j]]);

                if (i != 0)
                {
                    return i;
                }
            }

            return 0;
        }

        /**
         * Compare two rows of the table for inserting rows into unique indexes
         *
         * @param a data
         * @param b data
         *
         * @return comparison result, -1,0,+1
         *
         * @ 
         */
        private int compareRowForInsert(Session session, Row newRow,
                                        Row existingRow)
        {

            Object[] a = newRow.getData();
            Object[] b = existingRow.getData();
            int j = 0;
            bool hasNull = false;

            for (; j < colIndex.Length; j++)
            {
                Object currentvalue = a[colIndex[j]];
                int i = Column.compare(collation, currentvalue, b[colIndex[j]],
                                       colTypes[j]);

                if (i != 0)
                {
                    return i;
                }

                if (currentvalue == null)
                {
                    hasNull = true;
                }
            }

            if (_isUnique && !useRowId && !hasNull)
            {
                return 0;
            }

            for (j = 0; j < pkCols.Length; j++)
            {
                Object currentvalue = a[pkCols[j]];
                int i = Column.compare(collation, currentvalue, b[pkCols[j]],
                                       pkTypes[j]);

                if (i != 0)
                {
                    return i;
                }
            }

            if (useRowId)
            {
                int difference = newRow.getPos() - existingRow.getPos();

                if (difference < 0)
                {
                    difference = -1;
                }
                else if (difference > 0)
                {
                    difference = 1;
                }

                return difference;
            }

            return 0;
        }

        /**
         * Returns a value indicating the order of different types of index in
         * the list of indexes for a table. The position of the groups of Indexes
         * _in the list _in ascending order is as follows:
         *
         * primary key index
         * unique constraint indexes
         * autogenerated foreign key indexes for FK's that reference this table or
         *  tables created before this table
         * user created indexes (CREATE INDEX)
         * autogenerated foreign key indexes for FK's that reference tables created
         *  after this table
         *
         * Among a group of indexes, the order is based on the order of creation
         * of the index.
         *
         * @return ordinal value
         */
        public int getIndexOrderValue()
        {          

            if (_isConstraint)
            {
                return _isForward ? 4
                                 : _isUnique ? 0
                                            : 1;
            }
            else
            {
                return 2;
            }
        }

        private IndexRowIterator getIterator(Session session, Node x)
        {

            if (x == null)
            {
                return _emptyIterator;
            }
            else
            {
                IndexRowIterator it = new IndexRowIterator(session, this, x);

                return it;
            }
        }

        public class IndexRowIterator : RowIterator
        {

            Session session;
            Index index;
            Node nextnode;
            public IndexRowIterator last;
            public IndexRowIterator _next;

            /**
             * When session == null, rows from all sessions are returned
             */
            public IndexRowIterator(Session session, Index index, Node node)
            {

                if (index == null)
                {
                    return;
                }

                this.session = session;
                this.index = index;
                this.nextnode = node;
            }

            public bool hasNext()
            {
                return nextnode != null;
            }

            public Row next()
            {

                if (hasNext())
                {
                    try
                    {
                        Row row = nextnode.getRow();

                        nextnode = index.next(nextnode);

                        return row;
                    }
                    catch (Exception e)
                    {
                        throw new InvalidOperationException(e.Message);
                    }
                }
                else
                {
                    return null;
                }
            }

            public void updateForDelete(Node node)
            {

                try
                {
                    if (node.Equals(nextnode))
                    {
                        nextnode = index.next(node);
                    }
                }
                catch (Exception) { }
            }

            public void link(IndexRowIterator other)
            {

                other._next = _next;
                other.last = this;
                _next.last = other;
                _next = other;
            }

            public void release()
            {

                if (last != null)
                {
                    last._next = _next;
                }

                if (_next != null)
                {
                    _next.last = last;
                }
            }
        }
    }
}
